package com.yz.arithmetic;

/**
 * 插入排序
 * @author yuanzheng
 * @date 2020/9/24-15:10
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = {21, 43, 35, 7, 19, 11, 13};
        insertSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i]; //插入的数
            int index = i - 1; //被插入的位置(准备和前一个数比较)
            while (index >= 0 && insertVal < arr[index]) { //如果插入的数比被插入的数小
                arr[index + 1] = arr[index]; //将把 arr[index] 向后移动
                index--; //让 index 向前移动
            }
            arr[index + 1] = insertVal; //把插入的数放入合适位置
        }
    }
}
